import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class question_22 {
}
//括号生成
class Solution_22 {
//    写一个递归函数
//    说明：Set 是一种不允许重复元素的集合，当向 Set 集合中添加重复元素时，添加操作会被忽略，不会报错也不会覆盖前者。
    public List<String> recursion(int n){
        Set<String> result_set=new HashSet<>();
        if(n==1){
            result_set.add("()");
            return new ArrayList<String>(result_set);
        }
        List<String> temp=recursion(n-1);
//        上一层的外面加上一对括号
        for (String s : temp) {
            result_set .add("("+s+")");
        }
        for (int i = 1; i < n; i++) {
            List<String> temp1=recursion(i);
            List<String> temp2=recursion(n-i);
            for(String s1:temp1){
                for (String s2:temp2){
                    result_set.add(s1+s2);
                }
            }
        }
        return new ArrayList<String>(result_set);
    }
    public List<String> generateParenthesis(int n) {
        return recursion(n);
    }

    public static void main(String[] args) {
        Solution_22 s = new Solution_22();
        System.out.println(s.generateParenthesis(4));

    }
}